import java.util.Deque;
import java.util.LinkedList;

public class QueueAndStack {
    public Deque<Integer> q1;
    public Deque<Integer> q2;

    public QueueAndStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        // 1.两个队列都为空，则将x入到q1中
        if (empty()) {
            q1.offer(x);
            return;
        }
        // 2.q1不为空，则将x入到q1中
        if (!q1.isEmpty()) {
            q1.offer(x);
        } else {
            // 3.q2不为空，则将x入到q2中
            q2.offer(x);
        }

    }

    public int pop() {
        // 1.两个队列都为空,返回-1;
        if (empty()) {
            return -1;
        }
        // 2.q1不为空，将q1中size-1的元素入到q2中，q1中剩下的元素就是出队的元素;
        if (!q1.isEmpty()) {
            int len1 = q1.size();
            for (int i = 0; i < len1 - 1; i++) {
                q2.offer(q1.poll());
            }
            return q1.poll();
        } else {
            // 3.q2不为空，将q2中size-1的元素入到q1中，q2中剩下的元素就是出队的元素;
            int len2 = q2.size();
            for (int i = 0; i < len2 - 1; i++) {
                q1.offer(q2.poll());
            }
            return q2.poll();
        }
    }

    public int top() {
        // 1.两个队列都为空,返回-1;
        if (empty()) {
            return -1;
        }
        // 2.q1不为空，将q1中size-1的元素入到q2中，q1中剩下的元素就是出队的元素;
        if (!q1.isEmpty()) {
            int len1 = q1.size();
            int tmp = -1;
            for (int i = 0; i < len1; i++) {
                tmp = q1.poll();
                q1.offer(tmp);
            }
            return tmp;
        } else {
            // 3.q2不为空，将q2中size-1的元素入到q1中，q2中剩下的元素就是出队的元素;
            int len2 = q2.size();
            int tmp = -1;
            for (int i = 0; i < len2; i++) {
                tmp = q2.poll();
                q2.offer(tmp);
            }
            return tmp;
        }
    }

    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }

    public static void main(String[] args) {
        QueueAndStack queueAndStack = new QueueAndStack();
        queueAndStack.push(1);
        queueAndStack.push(2);
        queueAndStack.push(3);
        System.out.println(queueAndStack.top());
        System.out.println(queueAndStack.pop());
        System.out.println(queueAndStack.top());
        System.out.println(queueAndStack.pop());
        System.out.println(queueAndStack.top());
        System.out.println(queueAndStack.empty());
        System.out.println(queueAndStack.pop());
        System.out.println(queueAndStack.empty());


    }
}
